package com.example.arithmeticleetcode.learnArithmetic.graph;

import java.util.List;
import java.util.Set;

/**
 * @program: arithmetic-leetcode
 * @description: 分邻接表 和 矩阵
 * @author: FangZhen
 * @create: 2020-11-17 10:31
 **/
public abstract class Graph<V, E> {

    protected WeightManager<E> weightManager;

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    public Graph() {
    }

    public abstract int edgesSize();

    public abstract int verticesSize();

    /**
     * 添加节点
     *
     * @param v
     */
    public abstract void addVertext(V v);

    /**
     * 添加表
     *
     * @param from
     * @param to
     */
    public abstract void addEdge(V from, V to);

    /**
     * 添加表 并附带权值
     *
     * @param from
     * @param to
     * @param weight
     */
    public abstract void addEdge(V from, V to, E weight);

    /**
     * 删除节点
     *
     * @param v
     */
    public abstract void removeVertext(V v);

    /**
     * 删除边
     *
     * @param from
     * @param to
     */
    public abstract void removeEdge(V from, V to);

//    /**
//     * 广度优先搜索  breadth first search
//     *
//     * @param begin
//     */
//    void bfs(V begin);
//
//    /**
//     * 深度优先搜索 deepth first search
//     *
//     * @param begin
//     */
//    void dfs(V begin);


    /**
     * 广度优先搜索  breadth first search
     *
     * @param begin
     * @param vertexVisitor
     */
    public abstract void bfs(V begin, VertexVisitor<V> vertexVisitor);

    /**
     * 深度优先搜索 deepth first search
     *
     * @param begin
     * @param vertexVisitor
     */
    public abstract void dfs(V begin, VertexVisitor<V> vertexVisitor);

    /**
     * 有向无环图 拓扑排序
     *
     * @return
     */
    public abstract List<V> topologicalSort();

    /**
     * 最小生成树
     *
     * @return
     */
    public abstract Set<EdgeInfo<V, E>> mst();


    public interface VertexVisitor<V> {
        Boolean visit(V v);
    }

    public interface WeightManager<E> {
        int compare(E w1, E w2);
        E add(E w1, E w2);
    }

    public static class EdgeInfo<V, E> {
        private V from;
        private V to;
        private E weight;

        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public E getWeight() {
            return weight;
        }

        public void setWeight(E weight) {
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
}
